package Hot100.Medium.GreedyAndDP.DynamicPlanning.Rob;

import java.util.Arrays;

public class LC198 {
    public static void main(String[] args) {

    }

    public int rob(int[] nums){
        int f0 = 0;
        int f1 = 0;
        for(int num : nums){
            int newF = Math.max(f0 + num, f1); // 计算到目前抢到的钱。要么是f0+该位置的钱，要么就是f1
            // 更新位置，逐步向后移，也就是滚动数组，是一个常见的降低空间复杂度的办法
            f0 = f1;
            f1 = newF;
        }
        return f1;
    }

    /**
     * 递归搜索 + 保存计算结果 = 记忆化搜索
     * @param nums
     * @return
     */
    public int rob2(int[] nums){
        int n = nums.length;
        int[] memo = new int[n];
        Arrays.fill(memo, -1);// 把数组 array 的 所有元素 都赋值为 -1
        return dfs(n - 1, nums, memo);

    }

    // dfs(i)表示从nums[0]到nums[i]最多能偷多少
    private int dfs(int i, int[] nums, int[] memo){
        if (i < 0) {
            return 0;
        }
        if(memo[i] != -1){ // 之前计算过
            return memo[i];
        }
        int notChoose = dfs(i - 1, nums, memo);// 不选的话，就是从剩余里面选
        int choose = dfs(i - 2, nums, memo) + nums[i];// 选的话就是选的值以及隔一个房子开始剩余的值
        memo[i] = Math.max(notChoose, choose); // 记忆化
        return memo[i];
    }
}
